\section{Background}
\label{sec:background}
In this section we mainly introduce the MapReduce programming model,
OpenCL language,  and APARAPI APIs.


\subsection{MapReduce Programming Model}
MapReduce is a high-level programming model aiming at facilitating
parallel programming by masking the details of the underling
architecture. Programmers need only to write their applications
as two functions: the \textit{map} function and the \textit{reduce}
function. All of the inputs and outputs are represented as
\textit{key/value} pairs. Implementing a MapReduce framework involves
implementing three phases: the \textit{map} phase, the \textit{group}
phase, and the \textit{reduce} phase. Specifically, the MapReduce
framework first partitions the input dataset among the participating
parties (e.g. threads). Each party then applies the map function to
its assigned portion and writes the intermediate output (map phase).
The framework groups all of the intermediate outputs by their keys
(group phase). Finally, one or more keys of the grouped intermediate
outputs are assigned to each party, which will carry out the reducing
function and write out the result key/value pairs (reduce phase).

MapReduce was first proposed by Google~\cite{map-reduce-paper} in 2004.
It seeks to simplify parallel programming on large-scale clusters of
computers. The success of MapReduce on porting scientific and engineering
application to large-scale cluster motivated other MapReduce
implementations on different platforms. In Sec.~\ref{sec:related}, we
will discuss different MapReduce implementations categorized based on
the target platform.


\subsection{OpenCL}
Open Computing Language (OpenCL)~\cite{website:opencl} is a programming
framework and industry standard for heterogeneous computing resources
consisting of CPUs, GPUs, and other processors. With OpenCL, user can
write accelerated portable code across different devices and architectures
with decreased complexity.

As shown in Fig.~\ref{fig:opencl}, in OpenCL platform model~\cite{opencl-overview},
one CPU-based \textit{host} manages several different \textit{Compute Devices}
(CPUs and GPUs). Each \textit{Compute Device} consists of multiple \textit{Compute Units}
and each \textit{Compute Unit} consists of multiple \textit{Processing Elements}.
At the lowest level, each \textit{Processing Element} executes OpenCL kernel.
For any typical OpenCL application, a CPU host first defines an N-dimensional
computation domain over DRAM memory. Every index of this domain will be a
\textit{work-item} and each work-item launches the same kernel. The host then defines
\textit{work-items} into \textit{work-groups}. Each \textit{work-item} in
group will execute concurrently within a compute unit and will share some
local memory. These \textit{work-groups} are placed into a \textit{work-queue}.
The hardware will then load DRAM memory into the global GPU RAM and execute
each \textit{work-group} on the \textit{work-queue}.

\begin{figure}
 \vspace{1.0ex}
 \centering
 \begin{minipage}[t]{0.90\columnwidth}
   \includegraphics[width=\columnwidth]{figures/opencl}
 \end{minipage}
 \caption{OpenCL Platform Model}
 \label{fig:opencl}
 \vspace{-4.0ex}
\end{figure}

\subsection{APARAPI}
APARAPI~\cite{website:aparapi} is an open source interface that can provide
JIT compilation of Java bytecode to OpenCL kernels and the execution of those
kernels on heterogeneous devices. It supports a limited set of bytecode specification,
for example, it only allows pritimitve types and single-dimensional arrays of
primitives. APARAPI manages kernel translation, OpenCL memory allocation, data
transfers and kernel invocation and makes them completely transparent to the user.
By using it, users can take advantage of GPU computing power rather than being
restricted on CPUs. Fig.~\ref{fig:aparapi} shows the execution work flow of
APARPI framework.

\begin{figure}
 \vspace{2.0ex}
 \centering
 \begin{minipage}[t]{0.90\columnwidth}
   \includegraphics[width=\columnwidth]{figures/aparapi}
 \end{minipage}
 \caption{Execution Work Flow of APARAPI Framework}
 \label{fig:aparapi}
 \vspace{-4.0ex}
\end{figure}


